from copy import deepcopy


class Solution:
    def exist(self, board, word: str) -> bool:
        self.len_word = len(word)
        if self.len_word == 0:
            return True
        self.max_i, self.max_j = len(board), len(board[0])
        self.word, self.board = word, board
        for i in range(self.max_i):
            for j in range(self.max_j):
                if self.search(i, j, 0):
                    return True
        return False

    def search(self, i, j, zhizheng):
        if self.board[i][j] != self.word[zhizheng]:
            return False
        if zhizheng == self.len_word - 1:
            return True
        mid_word, self.board[i][j] = self.board[i][j], 0
        if i + 1 < self.max_i:
            if self.search(i+1, j, zhizheng+1):
                return True
        if i - 1 >= 0:
            if self.search(i-1, j, zhizheng+1):
                return True
        if j + 1 < self.max_j:
            if self.search(i, j+1, zhizheng+1):
                return True
        if j - 1 >= 0:
            if self.search(i, j-1, zhizheng+1):
                return True
        self.board[i][j] = mid_word
        return False


if __name__ == '__main__':
    a = Solution()
    b = [['A','B','C','E'],
         ['S','F','C','S'],
         ['A','D','E','E']]
    print(a.exist(b, "ABCDE"))  # F
    print(a.exist(b, "SEE"))  # T
    print(a.exist(b, "ABCB"))  # F
    print(a.exist(b, ""))  # T
    print(a.exist([[]], "a"))  # F
    print(a.exist([["a"]], "b"))  # F
    print(a.exist([["a", "b"]], "a"))  # T
    print(a.exist([["C","A","A"],["A","A","A"],["B","C","D"]], "AAB"))  # T